#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <inttypes.h>

#include "../include/contest_interface.h"
#include "../include/util.h"
#include "../include/QuadTree.h"
#include "../include/QLeafNode.h"
#include "../include/QInternalNode.h"
#include "../include/QNode.h"
#include "../include/Iterator.h"

QuadTree::QuadTree(void) {
    int a = 0;
    a++;
}

QuadTree::QuadTree(uint8_t dim, KeyType type) {
    this->dimension = dim;
    this->keyType = new AttributeType[dim];
    for (int i = 0; i < dim; i++)
        this->keyType[i] = type[i];
    this->root = new QLeafNode(NULL, 0);
}

QuadTree::~QuadTree(void) {
    // TODO release memory
}

void InsertSort(Record* r, std::list< Record*>* sortedListRecordPointer) {
    std::list< Record*>::iterator it;
    bool inserted = false;
    for (it = (*sortedListRecordPointer).begin(); it != (*sortedListRecordPointer).end(); it++)
        // override attcmp for equal
        // List = 2  2 3 4  8  9 10
        // Record =5  cmp(2,3)<0 cmp(4,3)>0
        // insert 3 at the position where 4 is present
        if (keycmp_sort((*it)->key, r->key) > 0) {
            (*sortedListRecordPointer).insert(it, r);
            inserted = true;
            break;
        }

    if (!inserted)
        (*sortedListRecordPointer).push_back(r);
}

void QuadTree::sortBucketList(QLeafNode* currentL, std::list< Record*>* sortedListRecord) {
    std::list< Record*>::iterator it;
    for (it = currentL->bucket.records.begin(); it != currentL->bucket.records.end(); it++)
        InsertSort(*(it), sortedListRecord);
}

void QuadTree::setSplitter(Key k, QInternalNode* qInternalNode) {
    qInternalNode->splitter.attribute_count = k.attribute_count;
    for (int i = 0; i < k.attribute_count; i++) {
        switch (k.value[i]->type) {
            case kShort:
            {
                qInternalNode->splitter.value[i]->type = kShort;
                qInternalNode->splitter.value[i]->short_value = k.value[i]->short_value;
                break;
            }
            case kInt:
            {
                qInternalNode->splitter.value[i]->type = kInt;
                qInternalNode->splitter.value[i]->int_value = k.value[i]->int_value;
                break;
            }
            case kVarchar:
            {
                qInternalNode->splitter.value[i]->type = kVarchar;
                strcpy(qInternalNode->splitter.value[i]->char_value, k.value[i]->char_value);
                break;
            }
        }
    }
}

QInternalNode* QuadTree::splitOptimal(QLeafNode* currentL) {
    //First sort the bucket before splitting to find median and then split on the basis of that median
    try {
        std::list< Record*> BucketList;
        this->sortBucketList(currentL, &BucketList);

        std::list< Record*>::iterator it;

        int counter = 0;
        int count = currentL->bucket.record_count / 2; //&& counter<count if countList=3 count=1

        //To find median of list of records to be set as  splitter
        for (it = BucketList.begin(); it != BucketList.end(); it++) {
            if (++counter >= count)
                break;
        }

        QInternalNode* newInternalNode = new QInternalNode(this->dimension);
        if (currentL->parent != NULL)
            currentL->parent->childs[currentL->childID] = newInternalNode;
        else
            this->root = newInternalNode;

        setSplitter((*it)->key, newInternalNode);

        for (it = currentL->bucket.records.begin(); it != currentL->bucket.records.end(); it++) {

            uint32_t bucketNum = keycmp_qtree((*it)->key, newInternalNode->splitter);
            //Just moving the pointers from QLeafNode to new childs(QLeafNode) of newInternalNode
            ((QLeafNode*) (newInternalNode->childs[bucketNum]))->insertBucketRecord(*it);

        }

        //Set the right of currentL->left to this first non null child
        if (currentL->nextLeftLeafNode != NULL) {
            ((QLeafNode*) newInternalNode->childs[0])->nextLeftLeafNode = currentL->nextLeftLeafNode;
            currentL->nextLeftLeafNode->nextRightLeafNode = (QLeafNode*) newInternalNode->childs[0];
        }

        //Sets right pointer for the parent's last non-null child to parent's right pointer
        if (currentL->nextRightLeafNode != NULL) {
            ((QLeafNode*) newInternalNode->childs[newInternalNode->childs_count - 1])->nextRightLeafNode =
                    currentL->nextRightLeafNode; //Means now we have to set the right pointer of i to parent right pointer of parent
            currentL->nextRightLeafNode->nextLeftLeafNode =
                    (QLeafNode*) newInternalNode->childs[newInternalNode->childs_count - 1];
        }
        //Free memory for list,bucket and currentL (QLeafNode*)
        currentL->bucket.records.clear();
        currentL->destruct(false);
        delete currentL;

        return newInternalNode;
    }//TODO: EXCEPTION HANDLE + FREE THE POINTERS
    catch (std::bad_alloc &e) {
        throw (kErrorOutOfMemory);
    } catch (ErrorCode &e) {
        throw (e);
    } catch (...) {
        throw (kErrorGenericFailure);
    }
    return NULL;
}

ErrorCode QuadTree::can_InsertRecord(Record * record, Transaction * tx) {
    QLeafNode* qLeafNode;
    try {
        qLeafNode = searchBucket_InsertRecord(record);
        if (qLeafNode != NULL)
            return kOk;
        //acquire lock on bucket/tree and then update the flags for that
        // particular record and if lock is successful
        // return kOk else return kGenericFailure
        return kErrorGenericFailure;
    } catch (std::bad_alloc &e) {
        throw kErrorOutOfMemory;
    } catch (ErrorCode &e) {
        throw e;
    } catch (...) {
        throw kErrorGenericFailure;
    }
    return kOk;
}

ErrorCode QuadTree::can_ModifyRecord(Record * record, Transaction * tx, uint8_t duplicateFlag,
        Iterator** itRecords) {
    QLeafNode* qLeafNode;
    try {
        qLeafNode = searchBucket_ModifyRecord(record);
        if (qLeafNode != NULL) {
            ErrorCode errCode;
            if ((duplicateFlag & (kMatchDuplicates | kIgnorePayload)) == 3) { //Case 3
                errCode = qLeafNode->fakeModifyRecord(&record->key, itRecords, true);
            } else if ((duplicateFlag & kMatchDuplicates) == 1) { //Case 1
                errCode = qLeafNode->fakeModifyRecord(record, itRecords, true);
            } else if ((duplicateFlag & kIgnorePayload) == 2) { // Case 2
                errCode = qLeafNode->fakeModifyRecord(&record->key, itRecords, false);
            } else { //Case 0
                errCode = qLeafNode->fakeModifyRecord(record, itRecords, false);
            }
            return errCode;
        } else
            return kErrorNotFound; //if(it!=NULL ends) means bucket not found means record not exists

        // acquire lock on bucket/tree qLeafNode->bucket and then update
        // the flags for that particular record and if lock is successful
        // return kOk else return kGenericFailure
    } catch (std::bad_alloc &e) {
        throw kErrorOutOfMemory;
    } catch (ErrorCode &e) {
        throw e;
    } catch (...) {
        throw kErrorGenericFailure;
    }
    return kOk;
}

QLeafNode * QuadTree::searchBucket_InsertRecord(Record * record) {
    QNode *n = this->root;
    while (n->getType() == 1) {
        uint32_t bucketNum = keycmp_qtree(record->key, ((QInternalNode*) n)->splitter);
        n = ((QInternalNode*) n)->childs[bucketNum];
    }
    return (QLeafNode*) n;
}

QLeafNode * QuadTree::searchBucket_ModifyRecord(Record * record) {
    QNode *n = this->root;
    while (n->getType() == 1) {
        uint32_t bucketNum = keycmp_qtree(record->key,
                ((QInternalNode*) n)->splitter);
        if (((QInternalNode*) n)->childs[bucketNum] != NULL)
            n = ((QInternalNode*) n)->childs[bucketNum];
        else
            return NULL;
    }
    return (QLeafNode*) n;
}

/**
 * @return
 *  - \ref kOk
 *          if the record was successfully inserted
 *  - \ref kErrorOutOfMemory
 *          if the operation was not completed because of a lack of free memory
 *  - \ref kErrorGenericFailure
 *          if the record could not be inserted for some other reason
 */
ErrorCode QuadTree::insert(Record * _record) {
    ErrorCode errCode;
    try {
        QLeafNode *currentL;

        currentL = searchBucket_InsertRecord(_record);
        if (currentL == NULL) {
            return kErrorGenericFailure;
        }

        if (currentL->bucket.record_count < MAX_LEAF_SIZE) {
            errCode = (currentL)->insertBucketRecord(_record);
            return errCode;
        } else {
            QInternalNode* splittedInternalNode = this->splitOptimal(currentL);
            if (splittedInternalNode != NULL) {

                //Adjust pointers for the first and last child of the newly created Internal Node by preserving left and right pointers of previous leafNode
                // ((QLeafNode*)(splittedInternalNode->childs[0]))->nextLeftLeafNode=currentL->nextLeftLeafNode;
                // ((QLeafNode*)(splittedInternalNode->childs[currentL->bucket.record_count-1]))->nextRightLeafNode=currentL->nextRightLeafNode;

                uint32_t bucketNum = keycmp_qtree(_record->key, splittedInternalNode->splitter);
                errCode = ((QLeafNode*) (splittedInternalNode->childs[bucketNum]))->insertBucketRecord(
                        _record);
                return errCode;
            }
            //else do exception handling here if the split was unsuccessful
            return kErrorGenericFailure;
        }
    } catch (std::bad_alloc &e) {
        throw kErrorOutOfMemory;
    } catch (ErrorCode &e) {
        throw e;
    } catch (...) {
        throw kErrorGenericFailure;
    }
    return kOk;
}

/**
 * Delete Record return codes
 *
 * @return ErrorCode
 * - \ref kOK
 *          if the record was successfully deleted
 * - \ref kErrorNotFound
 *          if the given record could not be found
 * - \ref kErrorGenericFailure
 *          if the record could not be deleted for some other reason
 */
ErrorCode QuadTree::delete_Record(Record *record, const uint8_t duplicateFlag) {
    try {
        QLeafNode* leafNode = searchBucket_ModifyRecord(record);
        ErrorCode errCode;

        if (leafNode == NULL) //Modified by Basmah @ 11 march 2012, now leafNOde should be present always coz of static creation
            return kErrorGenericFailure;

        if (leafNode->bucket.record_count != 0) {
            if ((duplicateFlag & (kMatchDuplicates | kIgnorePayload)) == 3) {
                errCode = leafNode->deleteBucketRecord(&record->key, true);
            } else if ((duplicateFlag & kMatchDuplicates) == 1) {
                errCode = leafNode->deleteBucketRecord(record, true);
            } else if ((duplicateFlag & kIgnorePayload) == 2) {
                errCode = leafNode->deleteBucketRecord(&record->key, false);
            } else {
                errCode = leafNode->deleteBucketRecord(record, false);
            }
            //TODO: Give bucket address to garbageCollector Table for now, which will
            // release its memory from l->bucket and cause Node->child[bucketNum]=NULL at certain periodic time
            return errCode;
        } else
            return kErrorNotFound; //if(it!=NULL ends) means bucket not found means record not exists
    } catch (std::bad_alloc &e) {
        throw kErrorOutOfMemory;
    } catch (ErrorCode &e) {
        throw e;
    } catch (...) {
        throw kErrorGenericFailure;
    }
    return kOk;
}

/**
 * @return
 * - \ref kOk
 *           if the record was successfully updated
 * - \ref kErrorNotFound
 *           if the given record could not be found
 * - \ref kErrorOutOfMemory
 *           if the operation was not completed because of a lack of free memory
 * - \ref kErrorGenericFailure
 *           if the record could not be updated for some other reason
 */
ErrorCode QuadTree::update_Record(Record *record, Block *new_payload,
        uint8_t duplicateFlag) {
    //TODO: EXCEPTIONS HANDLE
    //const bool cond=kMatchDuplicates & kMatchDuplicates;
    try {
        QLeafNode* leafNode = searchBucket_ModifyRecord(record);
        ErrorCode errCode;

        if (leafNode != NULL) {
            if ((duplicateFlag & (kMatchDuplicates | kIgnorePayload)) == 3) { //Case 3
                errCode = leafNode->updateBucketRecord(&record->key, new_payload, true);
            } else if ((duplicateFlag & kMatchDuplicates) == 1) { //Case 1
                errCode = leafNode->updateBucketRecord(record, new_payload, true);
            } else if ((duplicateFlag & kIgnorePayload) == 2) { // Case 2
                errCode = leafNode->updateBucketRecord(&record->key, new_payload,
                        false);
            } else { //Case 0
                errCode = leafNode->updateBucketRecord(record, new_payload, false);
            }
            return errCode;
        } else
            return kErrorNotFound; //if(it!=NULL ends) means bucket not found means record not exists
    } catch (std::bad_alloc &e) {
        return kErrorOutOfMemory;
    } catch (ErrorCode &e) {
        return e;
    } catch (...) {
        return kErrorGenericFailure;
    }
    return kOk;
}

ErrorCode QuadTree::RangeSearch(Key min, Key max, Iterator ** iterator) {
    if (iterator == NULL)
        return kErrorGenericFailure;

    try {
        //Get bucket that contains the min
        QNode *start = this->root;
        QLeafNode *temp;

        while (start->getType() == 1) {
            uint32_t i = keycmp_qtree(min, ((QInternalNode*) start)->splitter); //i is bucketNum
            start = ((QInternalNode*) start)->childs[i];
        }

        QLeafNode *st = (QLeafNode*) start;
        temp = st;
        if (temp->bucket.record_count > 0)
            temp->findRange(&min, &max, iterator);

        //Get the bucket that contains the max
        QNode *end = this->root;
        while (end->getType() == 1) {
            uint32_t i = keycmp_qtree(max, ((QInternalNode*) end)->splitter); //i is bucketNum
            end = ((QInternalNode*) end)->childs[i]; //make sure this logic will always get you to left nod
        }
        QLeafNode *en = (QLeafNode*) end;

        while (temp != en) {
            if (temp->bucket.record_count > 0) {
                temp = temp->nextRightLeafNode;
                temp->findRange(&min, &max, iterator);
            }
        }
    } catch (std::bad_alloc &e) {
        return kErrorOutOfMemory;
    } catch (ErrorCode &e) {
        return e;
    } catch (...) {
        return kErrorGenericFailure;
    }
    return kOk;
}

ErrorCode QuadTree::PointSearch(Key key, Iterator ** iterator) {
    try {
        QNode *n = this->root;
        while (n->getType() == 1) {
            uint32_t i = keycmp_qtree(key, ((QInternalNode*) n)->splitter); //i is bucketNum
            n = ((QInternalNode*) n)->childs[i];
        }

        QLeafNode *q = (QLeafNode*) n;
        if (q->bucket.record_count > 0) {
            q->find(&key, iterator);
        } else //Added by Basmah @ Mar11,2012 12:31 am , in case of bucket empty, it means return notFOund
            return kErrorNotFound;
    } catch (std::bad_alloc &e) {
        throw (kErrorOutOfMemory);
    } catch (ErrorCode &e) {
        throw (e);
    } catch (...) {
        throw (kErrorGenericFailure);
    }
    return kOk;
}

ErrorCode QuadTree::PartialSearch(Key key, Iterator ** records, std::vector< int> *ListNull,
        int nNull) {
    try {
        QNode *nRoot = this->root;

        if (nRoot->getType() == 1) //Internal Node
            PartialSearchHelper(key, (QInternalNode*) nRoot, records, ListNull, nNull);
        else
            ((QLeafNode*) nRoot)->findPartial(&key, records);
    } catch (std::bad_alloc &e) {
        throw kErrorOutOfMemory; //Changed from return to throw
    } catch (ErrorCode &e) {
        throw e;
    } catch (...) {
        throw kErrorGenericFailure;
    }
    return kOk;
}

ErrorCode QuadTree::PartialSearchHelper(Key key, QInternalNode *q, Iterator ** records,
        std::vector< int> *ListNull, int nNull) {
    try {
        std::list< int> *l = new std::list<int>();
        std::list< int>::iterator it;
        //    keycmp_partial(key, (Key) q->splitter, ListNull, nNull, l);
        for (it = l->begin(); it != l->end(); it++) {
            if (q->childs[*it] != NULL) {
                while (q->childs[*it]->getType() == 1) {
                    PartialSearchHelper(key, ((QInternalNode*) q->childs[*it]), records, ListNull, nNull);
                }
                QLeafNode *pLeaf = ((QLeafNode*) q->childs[*it]);
                (pLeaf->findPartial(&key, records));
            }
        }
    } catch (std::bad_alloc &e) {
        throw (kErrorOutOfMemory);
    } catch (ErrorCode &e) {
        throw (e);
    } catch (...) {
        throw (kErrorGenericFailure);
    }
    return kOk;
}
